//给定一个 没有重复 数字的序列，返回其所有可能的全排列。 
//
// 示例: 
//
// 输入: [1,2,3]
//输出:
//[
//  [1,2,3],
//  [1,3,2],
//  [2,1,3],
//  [2,3,1],
//  [3,1,2],
//  [3,2,1]
//] 
// Related Topics 回溯算法 
// 👍 854 👎 0

package leetcode.editor.cn;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

//Java：全排列
public class P46Permutations {
    public static void main(String[] args) {
        Solution solution = new P46Permutations().new Solution();
        // TO TEST
        int arr[]={1,2,3};
        solution.permute(arr);
        solution.print();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<List<Integer>> res=new ArrayList<>();
        public List<List<Integer>> permute(int[] nums) {
            if(nums==null||nums.length<=0){
                return res;
            }
            perm(nums,0,nums.length-1);
            return res;
        }

        public void perm(int[] arr, int k, int m) {
            if (k == m) {
                /*for (int e : arr) {
                    System.out.print(e + " ");
                }
                System.out.println();*/
                res.add(Arrays.stream(arr).boxed().collect(Collectors.toList()));
            } else {
                for (int i = k; i <= m; i++) {
                    swap(arr, k, i);
                    perm(arr, k + 1, m);
                    swap(arr, k, i);
                }
            }
        }

        private void swap(int[] arr, int k, int i) {
            int temp = arr[k];
            arr[k] = arr[i];
            arr[i] = temp;
        }

        private void print(){
            for(List<Integer> list:res){
                for(int e : list){
                    System.out.print(e+" ");
                }
                System.out.println();
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
